/* Copyright (c) 2006 by M Aamir Maniar 
 * 
 * Permission is hereby granted, free of charge, to any person obtaining 
 * a copy of this software and associated documentation files (the 
 * "Software"), to deal in the Software without restriction, including 
 * without limitation the rights to use, copy, modify, merge, publish, 
 * distribute, sublicense, and/or sell copies of the Software, and to 
 * permit persons to whom the Software is furnished to do so, subject to 
 * the following conditions:
 * 
 * The above copyright notice and this permission notice shall be 
 * included in all copies or substantial portions of the Software.
 * 
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 * 
 * */

namespace Generic.DataStructures
{
	using System;
	using System.Collections;
	using SysGeneric = System.Collections.Generic;
	using System.Diagnostics;
	using System.Text;
	using System.Runtime.Serialization;
	using Generic.Patterns;
	using Generic.Utils;

	/// <summary>
	/// Represents the singly linked list.
	/// </summary>
	/// <typeparam name="T">T is T.</typeparam>
	[Serializable]
	[DebuggerDisplay("Count = {Count}")]
	[DebuggerTypeProxy(typeof(Generic.DataStructures.SinglyLinkedList<>.SinglyLinkedListDebugView))]
	public class SinglyLinkedList<T> : SysGeneric.ICollection<T>, ISerializable, ICloneable
	{
		/****** Constructors *****/

		#region public SinglyLinkedList()
		/// <summary>
		/// Initializes a new instance of the <see cref="SinglyLinkedList&lt;T&gt;"/> class.
		/// </summary>
		public SinglyLinkedList()
		{
		}
		#endregion

		#region public SinglyLinkedList(LinkedList<T> linkedList)
		/// <summary>
		/// Initializes a new instance of the <see cref="SinglyLinkedList&lt;T&gt;"/> class.
		/// </summary>
		/// <param name="linkedList">The linked list.</param>
		public SinglyLinkedList(LinkedList<T> linkedList)
		{
			LinkedListNode<T> curNode = linkedList.Head;
			while (curNode != null)
			{
				Add(Prototype<T>.Clone(curNode.Value));
				curNode = curNode.Next;
			}
		}
		#endregion


		/***** ICollection<T> Members *****/

		#region void ICollection<T>.Add(T item)
		/// <summary>
		/// Adds an item to the <see cref="T:System.Collections.Generic.ICollection`1"></see>.
		/// </summary>
		/// <param name="item">The object to add to the <see cref="T:System.Collections.Generic.ICollection`1"></see>.</param>
		/// <exception cref="T:System.NotSupportedException">The <see cref="T:System.Collections.Generic.ICollection`1"></see> is read-only.</exception>
		void SysGeneric.ICollection<T>.Add(T item)
		{
			Add(item);
		}
		#endregion

		#region public virtual void Clear()
		/// <summary>
		/// Removes all items from the <see cref="T:System.Collections.Generic.ICollection`1"></see>.
		/// </summary>
		/// <exception cref="T:System.NotSupportedException">The <see cref="T:System.Collections.Generic.ICollection`1"></see> is read-only. </exception>
		public virtual void Clear()
		{
			_head = _tail = null;
			_count = 0;
		}
		#endregion

		#region public virtual bool Contains(T node)
		/// <summary>
		/// Determines whether [contains] [the specified node].
		/// </summary>
		/// <param name="node">The node.</param>
		/// <returns>
		/// 	<c>true</c> if [contains] [the specified node]; otherwise, <c>false</c>.
		/// </returns>
		public virtual bool Contains(T node)
		{
			if (Find(node) != null)
				return true;
			return false;
		}
		#endregion

		#region public virtual void CopyTo(T[] array, int arrayIndex)
		/// <summary>
		/// Copies the elements of the <see cref="T:System.Collections.Generic.ICollection`1"></see> to an <see cref="T:System.Array"></see>, starting at a particular <see cref="T:System.Array"></see> index.
		/// </summary>
		/// <param name="array">The one-dimensional <see cref="T:System.Array"></see> that is the destination of the elements copied from <see cref="T:System.Collections.Generic.ICollection`1"></see>. The <see cref="T:System.Array"></see> must have zero-based indexing.</param>
		/// <param name="arrayIndex">The zero-based index in array at which copying begins.</param>
		/// <exception cref="T:System.ArgumentOutOfRangeException">arrayIndex is less than 0.</exception>
		/// <exception cref="T:System.ArgumentNullException">array is null.</exception>
		/// <exception cref="T:System.ArgumentException">array is multidimensional.-or-arrayIndex is equal to or greater than the length of array.-or-The number of elements in the source <see cref="T:System.Collections.Generic.ICollection`1"></see> is greater than the available space from arrayIndex to the end of the destination array.-or-Type T cannot be cast automatically to the type of the destination array.</exception>
		public virtual void CopyTo(T[] array, int arrayIndex)
		{
			throw new Exception("The method or operation is not implemented.");
		}
		#endregion

		#region public virtual int Count
		int _count = 0;
		/// <summary>
		/// Gets the number of elements contained in the <see cref="T:System.Collections.Generic.ICollection`1"></see>.
		/// </summary>
		/// <value></value>
		/// <returns>The number of elements contained in the <see cref="T:System.Collections.Generic.ICollection`1"></see>.</returns>
		public virtual int Count
		{
			get
			{
				return _count;
			}
		}
		#endregion

		#region public virtual bool IsReadOnly
		/// <summary>
		/// Gets a value indicating whether the <see cref="T:System.Collections.Generic.ICollection`1"></see> is read-only.
		/// </summary>
		/// <value></value>
		/// <returns>true if the <see cref="T:System.Collections.Generic.ICollection`1"></see> is read-only; otherwise, false.</returns>
		public virtual bool IsReadOnly
		{
			get
			{
				return false;
			}
		}
		#endregion

		#region public bool Remove(T item)
		/// <summary>
		/// Removes the first occurrence of a specific object from the <see cref="T:System.Collections.Generic.ICollection`1"></see>.
		/// </summary>
		/// <param name="item">The object to remove from the <see cref="T:System.Collections.Generic.ICollection`1"></see>.</param>
		/// <returns>
		/// true if item was successfully removed from the <see cref="T:System.Collections.Generic.ICollection`1"></see>; otherwise, false. This method also returns false if item is not found in the original <see cref="T:System.Collections.Generic.ICollection`1"></see>.
		/// </returns>
		/// <exception cref="T:System.NotSupportedException">The <see cref="T:System.Collections.Generic.ICollection`1"></see> is read-only.</exception>
		public bool Remove(T item)
		{
			SinglyLinkedListNode<T> node = Find(item);
			if (node != null)
			{
				Remove(item);
				return true;
			}
			return false;
		}
		#endregion

		/********** IEnumerable<T> Members  ***********/

		#region public virtual IEnumerator<T> GetEnumerator()
		/// <summary>
		/// Returns an enumerator that iterates through the collection.
		/// </summary>
		/// <returns>
		/// A <see cref="T:System.Collections.Generic.IEnumerator`1"></see> that can be used to iterate through the collection.
		/// </returns>
		public virtual SysGeneric.IEnumerator<T> GetEnumerator()
		{
			SinglyLinkedListNode<T> curNode = Head;
			while (curNode != null)
			{
				yield return curNode.Value;
				curNode = curNode.Next;
			}
		}

		#endregion

		/********** IEnumerable Members  ***********/

		#region IEnumerator IEnumerable.GetEnumerator()
		/// <summary>
		/// Returns an enumerator that iterates through a collection.
		/// </summary>
		/// <returns>
		/// An <see cref="T:System.Collections.IEnumerator"></see> object that can be used to iterate through the collection.
		/// </returns>
		IEnumerator IEnumerable.GetEnumerator()
		{
			return GetEnumerator() as IEnumerator;
		}

		#endregion

		/********** SinglyLinkedList<T> Members  ***********/

		#region public virtual SinglyLinkedListNode<T> Head
		GSafeLinkedListNode _head = null;
		/// <summary>
		/// Gets the head node of the <see cref="SinglyLinkedList&lt;T&gt;"/>.
		/// </summary>
		/// <value>The head node.</value>
		public virtual SinglyLinkedListNode<T> Head
		{
			get
			{
				return _head;
			}
		}
		#endregion

		#region public virtual SinglyLinkedListNode<T> Tail
		GSafeLinkedListNode _tail = null;
		/// <summary>
		/// Gets the tail node of the <see cref="SinglyLinkedList&lt;T&gt;"/>.
		/// </summary>
		/// <value>The tail node.</value>
		public virtual SinglyLinkedListNode<T> Tail
		{
			get
			{
				return _tail;
			}
		}
		#endregion

		#region public virtual SinglyLinkedListNode<T> AddFirst(T value)
		/// <summary>
		/// Adds the first.
		/// </summary>
		/// <param name="value">The value.</param>
		/// <returns></returns>
		public virtual SinglyLinkedListNode<T> AddFirst(T value)
		{
			ArgumentValidator.CheckIfNull<T>(value);
			GSafeLinkedListNode newNode = new GSafeLinkedListNode(value);
			AddFirst(newNode);
			return newNode;
		}
		#endregion

		#region public virtual void AddFirst(SinglyLinkedListNode<T> node)
		/// <summary>
		/// Adds the first.
		/// </summary>
		/// <param name="node">The node.</param>
		public virtual void AddFirst(SinglyLinkedListNode<T> node)
		{
			ArgumentValidator.CheckIfNull<SinglyLinkedListNode<T>>(node);
			if (node.List != null && node.List == this)
				throw new InvalidOperationException("Node already belong to list.");
			GSafeLinkedListNode safeNode = GetSafeNode(node);
			safeNode.SetNext(_head);
			safeNode.SetList(this);
			_head = safeNode;
			if (Count == 0)
				_tail = safeNode;

			_count++;
		}
		#endregion

		#region public virtual SinglyLinkedListNode<T> Add(T value)
		/// <summary>
		/// Adds the specified value.
		/// </summary>
		/// <param name="value">The value.</param>
		/// <returns></returns>
		public virtual SinglyLinkedListNode<T> Add(T value)
		{
			ArgumentValidator.CheckIfNull<T>(value);
			GSafeLinkedListNode newNode = new GSafeLinkedListNode(value);
			Add(newNode);
			return newNode;
		}
		#endregion

		#region public virtual void Add(SinglyLinkedListNode<T> node)
		/// <summary>
		/// Adds the specified node.
		/// </summary>
		/// <param name="node">The node.</param>
		public virtual void Add(SinglyLinkedListNode<T> node)
		{
			ArgumentValidator.CheckIfNull<SinglyLinkedListNode<T>>(node);
			if (node.List != null && node.List.Equals(this))
				throw new InvalidOperationException("Node already belong to list.");
			GSafeLinkedListNode safeNode = GetSafeNode(node);
			safeNode.SetList(this);
			if (Count == 0)
				_tail = _head = safeNode;
			else
			{
				_tail.SetNext(safeNode);
				_tail = safeNode;
			}
			_count++;
		}
		#endregion

		#region public virtual SinglyLinkedListNode<T> AddBefore(SinglyLinkedListNode<T> node, T value)
		/// <summary>
		/// Adds the before.
		/// </summary>
		/// <param name="node">The node.</param>
		/// <param name="value">The value.</param>
		/// <returns></returns>
		public virtual SinglyLinkedListNode<T> AddBefore(SinglyLinkedListNode<T> node, T value)
		{
			ArgumentValidator.CheckIfNull<T>(value);
			GSafeLinkedListNode safeNode = new GSafeLinkedListNode(value);
			AddBefore(node, safeNode);
			return safeNode;
		}
		#endregion

		#region public virtual void AddBefore(SinglyLinkedListNode<T> node)
		/// <summary>
		/// Adds the before.
		/// </summary>
		/// <param name="node">The node.</param>
		/// <param name="newNode">The new node.</param>
		public virtual void AddBefore(SinglyLinkedListNode<T> node, SinglyLinkedListNode<T> newNode)
		{
			ArgumentValidator.CheckIfNull<SinglyLinkedListNode<T>>(node);
			ArgumentValidator.CheckIfNull<SinglyLinkedListNode<T>>(newNode);
			if (node.List != null && node.List != this)
				throw new InvalidOperationException("Souce node does not belong to this list.");
			if (newNode.List != null && newNode.List == this)
				throw new InvalidOperationException("New node already belong to this list.");
			if (node.IsHead)
			{
				AddFirst(newNode);
				return;
			}
			GSafeLinkedListNode safeNode = node as GSafeLinkedListNode;
			GSafeLinkedListNode newSafeNode = newNode as GSafeLinkedListNode;
			GSafeLinkedListNode prevNode = FindPreviousNode(node) as GSafeLinkedListNode;
			if (prevNode == null)
			{
				newSafeNode.SetNext(Head);
				_head = newSafeNode;
			}
			else
			{
				newSafeNode.SetNext(prevNode.Next);
				prevNode.SetNext(newSafeNode);
			}
			newSafeNode.SetList(this);
			_count++;
		}
		#endregion

		#region public virtual SinglyLinkedListNode<T> AddAfter(SinglyLinkedListNode<T> node, T value)
		/// <summary>
		/// Adds the after.
		/// </summary>
		/// <param name="node">The node.</param>
		/// <param name="value">The value.</param>
		/// <returns></returns>
		public virtual SinglyLinkedListNode<T> AddAfter(SinglyLinkedListNode<T> node, T value)
		{
			ArgumentValidator.CheckIfNull<T>(value);
			GSafeLinkedListNode safeNode = new GSafeLinkedListNode(value);
			AddAfter(node, safeNode);
			return safeNode;
		}
		#endregion

		#region public virtual void AddAfter(SinglyLinkedListNode<T> node)
		/// <summary>
		/// Adds the after.
		/// </summary>
		/// <param name="node">The node.</param>
		/// <param name="newNode">The new node.</param>
		public virtual void AddAfter(SinglyLinkedListNode<T> node, SinglyLinkedListNode<T> newNode)
		{
			ArgumentValidator.CheckIfNull<SinglyLinkedListNode<T>>(node);
			ArgumentValidator.CheckIfNull<SinglyLinkedListNode<T>>(newNode);
			if (node.List != null && node.List != this)
				throw new InvalidOperationException("Souce node does not belong to this list.");
			if (newNode.List != null && newNode.List == this)
				throw new InvalidOperationException("New node already belong to this list.");

			GSafeLinkedListNode safeNode = node as GSafeLinkedListNode;
			GSafeLinkedListNode newSafeNode = newNode as GSafeLinkedListNode;
			newSafeNode.SetNext(safeNode.Next);
			newSafeNode.SetList(this);
			safeNode.SetNext(newSafeNode);
			if (safeNode.IsTail)
				_tail = newSafeNode;
			_count++;
		}
		#endregion

		#region public virtual SinglyLinkedListNode<T> Find(T value)
		public virtual SinglyLinkedListNode<T> Find(T value)
		{
			if (Head.Value.Equals(value))
				return Head;
			SinglyLinkedListNode<T> curNode = Head;
			do
			{
				if (curNode.Value.Equals(value))
					return curNode;
				curNode = curNode.Next;
			}
			while (curNode != null);
			return null;
		}
		#endregion

		#region virtual private GSafeLinkedListNode FindPreviousNode(SinglyLinkedListNode<T> node)
		public virtual SinglyLinkedListNode<T> FindPreviousNode(SinglyLinkedListNode<T> node)
		{
			if (Head == node)
				return null;
			GSafeLinkedListNode curNode = Head as GSafeLinkedListNode;
			do
			{
				if (curNode.Next == node)
					return curNode;
				curNode = curNode.Next as GSafeLinkedListNode;
			}
			while (curNode.Next != null);
			return null;
		}
		#endregion

		#region public virtual void Remove(SinglyLinkedListNode<T> node)
		public virtual void Remove(SinglyLinkedListNode<T> node)
		{
			if (node == null)
				throw new ArgumentNullException("Supplied value can not be null.");
			if (node.List != null && !node.List.Equals(this))
				throw new InvalidOperationException("Node to be removed must belong to current list.");
			if (node.IsHead)
			{
				_head = Head.Next as GSafeLinkedListNode;
				node.Dispose();
				--_count;
			}
			else
			{
				GSafeLinkedListNode safeNode = FindPreviousNode(node) as GSafeLinkedListNode;
				if (safeNode != null)
				{
					safeNode.SetNext(node.Next);
					--_count;
				}
			}
		}
		#endregion

		/***** ISerializable Members *****/

		#region public void GetObjectData(SerializationInfo info, StreamingContext context)
		public void GetObjectData(SerializationInfo info, StreamingContext context)
		{
			throw new Exception("The method or operation is not implemented.");
		}
		#endregion

		/***** ICloneable Members ****/

		#region object ICloneable.Clone()
		/// <summary>
		/// Creates a new object that is a copy of the current instance.
		/// </summary>
		/// <returns>
		/// A new object that is a copy of this instance.
		/// </returns>
		object ICloneable.Clone()
		{
			return this.Clone();
		}
		#endregion

		#region public SinglyLinkedList<T> Clone()
		/// <summary>
		/// Creates a new SinglyLinkedList that is a copy of the current instance.
		/// </summary>
		/// <returns>
		/// A new object that is a copy of this instance.
		/// </returns>
		public SinglyLinkedList<T> Clone()
		{
			Prototype<SinglyLinkedList<T>> proto = new Prototype<SinglyLinkedList<T>>(this);
			return proto.Clone();
		}

		#endregion

		/***** Protected *****/

		#region protected SinglyLinkedListNode<T> Find(SinglyLinkedList<T> list, T value)
		protected SinglyLinkedListNode<T> Find(SinglyLinkedList<T> list, T value)
		{
			if (list.Head.Value.Equals(value))
				return list.Head;
			SinglyLinkedListNode<T> curNode = list.Head;
			do
			{
				if (curNode.Next.Value.Equals(value))
				{
					return curNode;
				}
			}
			while (curNode.Next != null);
			return null;
		}
		#endregion

		#region private GSafeLinkedListNode GetSafeNode(SinglyLinkedListNode<T> node, SinglyLinkedList<T> list)
		protected GSafeLinkedListNode GetSafeNode(SinglyLinkedListNode<T> node)
		{
			GSafeLinkedListNode safeNode = node as GSafeLinkedListNode;
			if (safeNode == null)
				return new GSafeLinkedListNode(node, this);
			else
				return safeNode;
		}
		#endregion

		/***** Export Functions *****/

		#region public LinkedList<T> ToLinkedList()
		public SysGeneric.LinkedList<T> ToLinkedList()
		{
			return new SysGeneric.LinkedList<T>(this);
		}
		#endregion

		#region public T[] ToArray()
		public T[] ToArray()
		{
			T[] arr = new T[Count];
			int index = 0;
			SinglyLinkedListNode<T> curNode = Head;
			while (curNode != null)
			{
				arr[index++] = curNode.Value;
				curNode = curNode.Next;
			}
			return arr;
		}
		#endregion

		/***** Inner Classes *****/

		#region protected class GSafeLinkedListNode : SinglyLinkedListNode<T>
		protected class GSafeLinkedListNode : SinglyLinkedListNode<T>
		{

			#region public GSafeLinkedListNode(SinglyLinkedListNode<T> node):base(node.Value)
			public GSafeLinkedListNode(SinglyLinkedListNode<T> node, SinglyLinkedList<T> list)
				: base(node.Value)
			{
				SetList(list);
			}
			#endregion

			#region public GSafeLinkedListNode(T value)
			public GSafeLinkedListNode(T value)
				: base(value)
			{
			}
			#endregion

			#region public void SetNext(SinglyLinkedListNode<T> nextNode)
			public new void SetNext(SinglyLinkedListNode<T> nextNode)
			{
				base.SetNext(nextNode);
			}
			#endregion

			#region public void SetList(SinglyLinkedList<T> list)
			public new void SetList(SinglyLinkedList<T> list)
			{
				base.SetList(list);
			}
			#endregion

		}
		#endregion

		#region internal class SinglyLinkedListDebugView
		internal class SinglyLinkedListDebugView
		{
			SinglyLinkedList<T> _list;
			public SinglyLinkedListDebugView(SinglyLinkedList<T> list)
			{
				_list = list;
			}

			[DebuggerBrowsable(DebuggerBrowsableState.RootHidden)]
			public T[] Items
			{
				get
				{
					return _list.ToArray();
				}
			}


		}
		#endregion

	}
}
